package demo6;
import java.util.*;
public class Test {
    public  static List<String> topKFrequent(String[] words, int k) {
        //1. 需要去统计 每个单词出现的次数
        Map<String,Integer> map = new HashMap<>();
        for (String word : words) {
            if(map.get(word) == null) {
                map.put(word,1);
            }else {
                int val = map.get(word);
                map.put(word,val+1);
            }
        }
        //2. 通过上述代码 我们已经得到了，每个单词出现的次数，存储到了map当中
        // 也就是说，如果看哪个单词出现的频率，接下来要遍历的是map
        //2.1 创建小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());//根据key变成大根堆
                }
                //默认根据频率来创建小根堆
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        //3. 遍历map 把每个单词及频率获取到，存放到小根堆当中。以TOPK的问题去解决。
        for(Map.Entry<String,Integer> entry : map.entrySet()) {
            //entry ==> hello - 3
            if(minHeap.size() < k) {
                minHeap.offer(entry);// 扣5
            }else {
                //此时堆 放满了 ，需要每次和堆顶元素进行比较
                Map.Entry<String,Integer> top = minHeap.peek();
                //频率相同
                if(top.getValue().compareTo(entry.getValue()) == 0) {
                    if(top.getKey().compareTo(entry.getKey()) > 0) {
                        //堆顶是def-3, entry是 abc - 3. 出堆
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }else {
                    //频率不相同
                    // 堆顶是def-3, entry是 abc - 6. 出堆
                    if(entry.getValue().compareTo(top.getValue()) > 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                    // 堆顶是def-3, entry是 abc - 2. 不动
                }
            }
        }
        //3  4  8
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> tmp = minHeap.poll();
            ret.add(tmp.getKey());//def ab gh
        }
        Collections.reverse(ret);//gh  ab  def
        return ret;
    }

    public static void main(String[] args) {

        String words[] = {"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"};
        List<String> ret =topKFrequent(words,4);
        System.out.println(ret);
    }

}
